#include <iostream>
#include <unordered_map>
#include <list>
#include <iterator>

using namespace std;

// LCR 031. LRU 缓存
// https://leetcode.cn/problems/OrIXps/description/

class LRUCache
{
public:
    LRUCache(int capacity)
    :mCap(capacity)
    {
    }

    // 查
    int get(int key)
    {
        if(cacheMap.find(key) == cacheMap.end()){
            return -1;
        }
        // 存在
        int ans = cacheMap[key]->second;
        cacheList.splice(cacheList.end(), cacheList, cacheMap[key]);

        return ans;
    }

    // 增
    void put(int key, int value)
    {
        // 存在情况
        if(cacheMap.find(key) != cacheMap.end()){
            cacheMap[key]->second = value;
            cacheList.splice(cacheList.end(), cacheList, cacheMap[key]);
            return;
        }
        // 不存在情况

        // LRU已满，需淘汰
        if(cacheList.size() == mCap){
            cacheMap.erase(cacheList.begin()->first);
            cacheList.pop_front();
        }
        // 不需要淘汰
        cacheList.push_back({key, value});
        cacheMap[key] = std::prev(cacheList.end());
    }

private:
    int mCap;
    list<pair<int, int>> cacheList;
    unordered_map<int, list<pair<int, int>>::iterator> cacheMap;
};

int main()
{
    return 0;
}